package com.lry.basic.algorithm.sort;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/6/24
 */
public class QuickSort {
    public static void main(String[] args) {
        int [] arr = {3,2,6,1,7};
        QuickSort sort = new QuickSort();
        sort.quickSort(arr,0,4);
        for (int res :arr) {
            System.out.print(res+" ");
        }
    }
    public void quickSort(int[] arr,int i,int j){
        if(i<=j){
            int partition = partition(arr,i,j);
            quickSort(arr,i,partition-1);
            quickSort(arr,partition+1,j);
        }
    }

    /**
     * 一次划分函数
     * 例如 3 2 6 1 7
     *     i       j
     * 选择3作为轴值
     * 右侧扫描 7>3 j--
     * 3 2 6 1 7
     * i     j
     * 交换后i++
     * 1 2 6 3 7
     *   i   j
     * 左侧扫描
     * 1 2 6 3 7
     *     i j
     * 交换后j--
     * 1 2 3 6 7
     *    ij
     * @param arr
     * @param i
     * @param j
     * @return
     */
    public int partition(int[] arr,int i,int j){
        while(j>i){
            //右侧扫描
            while(j>i&&arr[j]>=arr[i]){
                j--;
            }
            //交换后i++
            if(j>i){
                swap(arr,i,j);
                i++;
            }

            //左侧扫描
            while(j>i&&arr[j]>=arr[i]){
               i++;
            }
            //交换后j--
            if(j>i){
                swap(arr,i,j);
                j--;
            }
        }
        return i;
    }
    public void swap(int[] arr, int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
